package com.cqs.leetcode;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 第一排序
 * 考虑极端情况来避免不必要的循环
 * Author:li
 * <p>
 * create date: 18-5-30 09:23
 */
public class Sum4_18 {

    //leetcode  33 ms
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 4) return result;
        Arrays.sort(nums);
        int sumLast2 = nums[nums.length - 1] + nums[nums.length - 2];
        int sumLast3 = sumLast2 + nums[nums.length - 3];
        for (int i = 0; i < nums.length - 3; i++) {
            //通过边界　减少不必要的循环
            if ((i > 0 && nums[i - 1] == nums[i]) || nums[i] + sumLast3 < target)
                continue;
            //后面的计算　一定会不会小于 nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3]
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                return result;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                int sum2 = nums[i] + nums[j];
                if ((j > i + 1 && nums[j - 1] == nums[j]) || (sum2 + sumLast2 < target))
                    continue;
                //后面的计算　一定会不会小于 sum0 + nums[i + 2] + nums[i + 3]
                if (sum2 + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                for (int k = j + 1; k < nums.length - 1; k++) {
                    int sum3 = sum2 + nums[k];
                    if ((k > j + 1 && nums[k - 1] == nums[k]) || (sum3 + nums[nums.length - 1] < target)) continue;
                    int idx = searchLast(nums, target - sum3);
                    //注意边界情况
                    if (idx != -1 && idx > k) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[idx]));
                    }
                }
            }
        }
        return result;
    }

    /**
     * 查询target在有序数组sort中最后一次出现的位置 若不存在返回-1
     *
     * @param sort
     * @param target
     * @return
     */
    private int searchLast(int[] sort, int target) {
        if (sort == null || sort.length == 0) return -1;
        int left = 0, right = sort.length - 1, mid = (left + right) / 2;
        do {
            if (target == sort[mid]) {
                //mid一定会小于等于right
                if (mid == right || sort[mid + 1] != target) return mid;
                left = mid + 1;
            } else if (target < sort[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        } while (left <= right);
        return -1;
    }


    //leetcode 23ms
    class Solution {
        public List<List<Integer>> fourSum(int[] num, int target) {
            ArrayList<List<Integer>> ans = new ArrayList<>();
            if (num.length < 4) return ans;
            Arrays.sort(num);
            for (int i = 0; i < num.length - 3; i++) {
                if (num[i] + num[i + 1] + num[i + 2] + num[i + 3] > target)
                    break; //first candidate too large, search finished
                if (num[i] + num[num.length - 1] + num[num.length - 2] + num[num.length - 3] < target)
                    continue; //first candidate too small
                if (i > 0 && num[i] == num[i - 1]) continue; //prevents duplicate result in ans list
                for (int j = i + 1; j < num.length - 2; j++) {
                    if (num[i] + num[j] + num[j + 1] + num[j + 2] > target) break; //second candidate too large
                    if (num[i] + num[j] + num[num.length - 1] + num[num.length - 2] < target)
                        continue; //second candidate too small
                    if (j > i + 1 && num[j] == num[j - 1]) continue; //prevents duplicate results in ans list
                    int low = j + 1, high = num.length - 1;
                    while (low < high) {
                        int sum = num[i] + num[j] + num[low] + num[high];
                        if (sum == target) {
                            ans.add(Arrays.asList(num[i], num[j], num[low], num[high]));
                            while (low < high && num[low] == num[low + 1]) low++; //skipping over duplicate on low
                            while (low < high && num[high] == num[high - 1]) high--; //skipping over duplicate on high
                            low++;
                            high--;
                        }
                        //move window
                        else if (sum < target) low++;
                        else high--;
                    }
                }
            }
            return ans;
        }
    }


    //6ms
    class Solution2 {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            //双指针
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<>();
            for (int i = 0; i < nums.length - 3; ++i) {
                //剪枝
                if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                for (int j = i + 1; j < nums.length - 2; ++j) {
                    int left = j + 1, right = nums.length - 1;
                    //剪枝
                    if ((nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)) break;
                    if ((j > i + 1 && nums[j] == nums[j - 1]) || (nums[i] + nums[j] + nums[right] + nums[right - 1]) < target) continue;
                    int t0 = target - nums[i] - nums[j];
                    //双指针
                    while (left < right) {
                        int s = nums[left] + nums[right];
                        if (s < t0) {
                            while (left < right && nums[left] == nums[++left]) ;
                        } else if (s > t0) {
                            while (left < right && nums[right] == nums[--right]) ;
                        } else {
                            result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                            while (left < right && nums[left] == nums[++left]) ;
                            while (left < right && nums[right] == nums[--right]) ;
                        }
                    }
                }
            }
            return result;
        }
    }


    public static void main(String[] args) {
        Sum4_18 s = new Sum4_18();
        int[] nums = {0, 0, 0, 0};
        List<List<Integer>> list = s.fourSum(nums, 0);
        System.out.println(list);
    }
}
